package a_doubleWrite;

/**
 * todo
 *
 * @author: luolidong
 * @create: 2021-07-20 09:00
 * @version: 1.0
 */
public class HeapSort {
    //建堆
    public void buildHeap(int[] nums) {
        int len = nums.length;
        for (int i = (len - 2) / 2; i >= 0; i--) {
            downAdjust(nums, i, len - 1);
        }
    }

    private void downAdjust(int[] nums, int parent, int len) {
        int temp = nums[parent];
        int child = parent * 2 + 1;//左孩子

        while (child <= len) {
            if (child + 1 <= len && nums[child] < nums[child + 1]) {
                child++;
            }
            if (nums[child] <= temp) {
                break;
            }
            //替换，继续向下
            nums[parent] = nums[child];
            parent = child;
            child = parent * 2 + 1;
        }
        nums[parent] = temp;
    }

    public int[] heapSort(int[] nums) {
        //1.建堆
        buildHeap(nums);
        //2.依次替换，调整
        int len = nums.length;
        for (int i = len - 1; i >= 1; i--) {
            int temp = nums[i];
            nums[i] = nums[0];
            nums[0] = temp;

            downAdjust(nums, 0, i - 1);
        }
        return nums;
    }
}
